package com.lft.linked.list05.queue_linked_list;

/**
 * 双端链表模拟队列
 */
public class QueueDoubleEndedLinkedListDemo {
	public static void main(String[] args) {
		QueueDoubleEndedLinkedList queue = new QueueDoubleEndedLinkedList();
		queue.insert(1);
		queue.insert(2);
		queue.insert(3);
		queue.insert(4);
		
		queue.displayQueue();
		
		queue.insert(5);
		queue.insert(6);
		
		queue.displayQueue();
		
		queue.remove();
		
		queue.displayQueue();
	}
}

class QueueDoubleEndedLinkedList {
	private FirstLastList list;
	
	public QueueDoubleEndedLinkedList() {
		list = new FirstLastList();
	}
	
	/**
	 * 判断链表是否为空。
	 * @return
	 */
	public boolean isEmpty() {
		return list.isEmpty();
	}
	
	/**
	 * 入队
	 * @param data
	 */
	public void insert(int data) {
		list.insertLast(data);
	}
	
	/**
	 * 出队
	 * @return
	 */
	public int remove() {
		return list.deleteFirst();
	}
	
	/**
	 * 遍历
	 */
	public void displayQueue() {
		System.out.println("Front -> Rear");
		list.displayList();
	}
}

/**
 * 双端链表类
 */
class FirstLastList {
	private Link first;
	private Link last;
	
	public FirstLastList() {
		first = null;
		last = null;
	}
	
	/**
	 * 判断链表是否为空
	 * @return boolean
	 */
	public boolean isEmpty() {
		return first == null;
	}
	
	/**
	 * 从头部插入
	 */
	public void insertFirst(int data) {
		Link newNode = new Link(data);
		if (isEmpty()) {
			last = newNode;
		}
		newNode.next = first;
		first = newNode;
	}
	
	/**
	 * 从尾部插入
	 */
	public void insertLast(int data) {
		Link newNode = new Link(data);
		if (isEmpty()) {
			first = newNode;
		} else {
			last.next = newNode;
		}
		last = newNode;
	}
	
	/**
	 * 删除第一个节点
	 * @return oldval {删除的结点值}
	 */
	public int deleteFirst() {
		int oldVal = first.data;
		if (first.next == null) {
			last = null;
		}
		first = first.next;
		return oldVal;
	}
	
	/**
	 * 双端链表的遍历
	 */
	public void displayList() {
		Link curr = first;
		while (curr != null) {
			curr.displayLink();
			curr = curr.next;
		}
		System.out.println();
	}
}

/**
 * 节点类
 */
class Link {
	public int data;
	public Link next;
	
	public Link(int data) {
		this.data = data;
	}
	
	public void displayLink() {
		System.out.print(data + "  ");
	}
}
